package tasks.leetcode.算法通关;

public class ClimbStairs {

    public static void main(String[] args) {
        int solution = new ClimbStairs().solution(10);
        int solution2 = new ClimbStairs().solution2(10);
        System.out.println("solution value:" + solution);
        System.out.println("solution value2 2:" + solution2);

    }
    public int solution2(int n) {
        if (n < 2) {
            return n;
        }
        int first =1;
        int second=2;
        for (int i = 3; i < n + 1; i++) {
            second = first + second;
            first = second - first;
        }
        return second;
    }
    public int solution(int n){
        if (n < 2) {
            return n;
        }
        int dp[] = new int[n+1];
        dp[0] =1;
        dp[1] =1;
        dp[2] = 2;
        for (int i = 3; i < n + 1; i++) {
            dp[i] = dp[i-1] + dp[i-2];
        }
        return dp[n];
    }

}
